Ban đầu, Schwartz sáng tác phiên bản sử dụng trong phim của "When You Believe", được biểu diễn bởi hai nhân vật Tzipporah (Michelle Pfeiffer) và Miriam (Sally Dworsky).[8] Ca khúc sử dụng một số nhạc cụ khác so với bản gốc và có thêm một đoàn hợp xướng thiếu nhi, cũng như vài dòng viết bằng tiếng Do Thái. Tuy nhiên, nhằm mục đích giúp cho ca khúc được phủ sóng rộng rãi hơn trên các đài phát thanh và nhận được sự quan tâm nhiều hơn của công chúng, Edmonds thay đổi một số nhạc cụ và thay thế dàn hợp xướng thiếu nhi bằng một dàn hợp xướng phúc âm.[8] Phiên bản của anh được cho là mang tính "thương mại" nhiều hơn và sẽ làm cho ca khúc "góp phần tăng doanh thu của bộ phim". Tựa đề bản gốc của Schwartz là "When You Believe", trong khi phiên bản mới của Edmonds được đặt tên là "The Prince of Egypt (When You Believe)".[8] "When You Believe" là một bản ballad có tiết tấu chậm, trong đó có sự kết hợp của pop và dòng contemporary R&B. Phần hát của Carey và Houston được viết ở các khóa khác nhau, đều có đủ phần nhạc và lời. Trong phần bridge và hát bè cuối, các ca sĩ phúc âm hát đệm tham gia vào bài hát, tạo nên một "lớp âm thanh" bên cạnh tiếng hát của Carey và Houston. Sau khi "When You Believe" được viết lời hoàn thiện, Babyface viết thêm phần nhạc cụ bổ sung, cũng như một phần bridge khép lại ca khúc.[5]

Bài hát được viết trên cùng một nhịp thời gian. Phần hát và bè của Houston được viết ở khóa Si thứ và có quãng hợp âm cơ bản từ A♭ đến G♭1. Quãng giọng của cô trong ca khúc trải dài từ nốt F♯3 đến nốt F♯5. Phần bè của Carey được viết ở khóa cao hơn, Mi trưởng và cũng được đặt ở cùng nhịp thời gian. Quãng giọng của cô trong bài kéo dài từ nốt G3 tới nốt cao G6, hơn một quãng tám so với giọng của Houston.[9] Phần quan trọng nhất của bài hát nằm ở phần bè cuối bài, được đặt trên khóa Fa thăng trưởng cao hơn. Steve Jones của USA Today gọi ca khúc là "một bản song ca bay bổng" và cảm thấy bài hát có sức lan tỏa với nhiều tầng lớp khán thính giả thuộc "tất cả những thể loại âm nhạc."[10]